#ifndef TREE_HPP
#define TREE_HPP
#include <cstdio>
#include <cstdlib>
#define MaxSize 100
#include "linkqueue.hpp"

// 二叉树的顺序存储
template <typename ElemType> struct TreeNodeInOrder {
  ElemType value; // 结点中的数据元素
  bool isEmpty;   // 结点是否为空
};

// 二叉树结点
template <typename ElemType> struct BiTNode {
  ElemType data;
  BiTNode *lchild, *rchild;
};

// 访问二叉树结点
template <typename ElemType> void visit(BiTNode<ElemType> *T) {
  printf("%d\t", T->data);
}

// 二叉树根
template <typename ElemType> using BiTree = BiTNode<ElemType> *;

// 二叉树的先序遍历
template <typename ElemType> void PreOrder(BiTree<ElemType> T) {
  if (T != nullptr) {
    visit(T);
    PreOrder(T->lchild);
    PreOrder(T->rchild);
  }
}

// 二叉树的中序遍历
template <typename ElemType> void InOrder(BiTree<ElemType> T) {
  if (T != nullptr) {
    InOrder(T->lchild);
    visit(T);
    InOrder(T->rchild);
  }
}

// 二叉树的后序遍历
template <typename ElemType> void PostOrder(BiTree<ElemType> T) {
  if (T != nullptr) {
    PostOrder(T->lchild);
    PostOrder(T->rchild);
    visit(T);
  }
}

// 二叉树的层次遍历
template <typename ElemType> void LevelOrder(BiTree<ElemType> T) {
  LinkQueue<BiTNode<ElemType> *> Q;
  BiTNode<ElemType> *p;
  Q.EnQueue(T);
  while (!Q.IsEmpty()) {
    Q.DeQueue(p);
    visit(p);
    if (p->lchild != nullptr)
      Q.EnQueue(p->lchild);
    if (p->rchild != nullptr)
      Q.EnQueue(p->rchild);
  }
}

// 线索二叉树结点
template <typename ElemType> struct ThreadNode {
  ElemType data;
  struct ThreadNode<ElemType> *lchild, *rchild;
  int ltag, rtag;
};
template <typename ElemType> using ThreadTree = ThreadNode<ElemType> *;

template <typename ElemType>
void InThread(ThreadTree<ElemType> &p, ThreadTree<ElemType> &pre) {
  if (p != nullptr) {
    InThread(p->lchild, pre);
    if (p->lchild == nullptr) {
      p->lchild = pre;
      p->ltag = 1;
    }
    if (pre != nullptr && pre->rchild == nullptr) {
      pre->rchild = p;
      pre->rtag = 1;
    }
    pre = p;
    InThread(p->rchild, pre);
  }
}

template <typename ElemType> void CreateInThread(ThreadTree<ElemType> T) {
  ThreadTree<ElemType> pre = nullptr;
  if (T != nullptr) {
    InThread(T, pre);
    pre->rchild = nullptr;
    pre->rtag = 1;
  }
}

// 找到以 p 为根的子树中，第一个被中序遍历的结点
template <typename ElemType>
ThreadNode<ElemType> *FirstNode(ThreadNode<ElemType> *p) {
  while (p->ltag == 0)
    p = p->lchild;
  return p;
}

template <typename ElemType>
ThreadNode<ElemType> *NextNode(ThreadNode<ElemType> *p) {
  if (p->rtag == 0)
    return FirstNode(p->rchild);
  else
    return p->rchild; // rtag=1直接返回后继搜索
}

template <typename ElemType> void InOrder(ThreadNode<ElemType> *T) {
  for (ThreadNode<ElemType> *p = FirstNode(T); p != nullptr; p = NextNode(p))
    visit(p);
}

// 找到以 p 为根的子树中，最后一个被中序遍历的结点
template <typename ElemType>
ThreadNode<ElemType> *LastNode(ThreadNode<ElemType> *p) {
  while (p->rtag == 0) {
    p = p->rchild;
  }
  return p;
}

template <typename ElemType>
ThreadNode<ElemType> *PreNode(ThreadNode<ElemType> *p) {
  if (p->ltag == 0)
    return LastNode(p->lchild);
  else
    return p->lchild;
}

// 对中序线索二叉树进行逆向中序遍历
template <typename ElemType> void RevInorder(ThreadNode<ElemType> *T) {
  for (ThreadNode<ElemType> *p = LastNode(T); p != nullptr; p = PreNode(p))
    visit(p);
}
#endif